When a transmitting end transmits data packets to a receiving end via a packet switched communication network, for instance via the Internet or an IP based wireless network, some of the data packets may be corrupted or lost on the way. It is therefore common practice to transmit in addition error correction data to the receiving end. The error correction data may enable the receiving end to restore corrupted or lost data to a considerable extent.
In order to minimize the amount of data which has to be transmitted, the error correction data may be transmitted, for example, only in case the receiving end does not acknowledge safe reception of a transmitted data packet. Using an acknowledgement protocol is not feasible for point-to-multipoint transmissions, though. For ensuring a reliable transmission in a multicast transmission, conventionally a Forward Error Correction (FEC) scheme is implemented. Such an FEC scheme includes sending by default a certain amount of redundant data, which can assist a receiving end in reconstructing erroneous or missing data.
For producing the redundant data for an FEC scheme, various types of coding can be employed. The Low Density Parity Code (LDPC) family comprises a class of FEC codes which result in encoded data that can be decoded efficiently using a message-passing algorithm over a graph. When used for erasure correction, the application of a message-passing algorithm is equivalent to solving a set of linear equations by recursive substitution. This type of decoding is also referred to as a chain reaction decoding.
A parity check matrix which is associated to the employed code uniquely determines the decoding graph or the set of linear equations which have to be solved. The parity check matrix H of a binary LDPC consists of ‘ones’ and ‘zeros’. The ‘ones’ are randomly placed in the column depending on the so-called degree distribution. The parity check matrix of binary LDPC has been dealt with for example in the document: “Low Density Parity-Check Codes”, MIT Press, Cambridge, Mass., 1963, by R. G. Gallager, to which it is referred.
There exist many types of LDPC codes that result in different decoding performances, depending on the dimensions of the LDPC parity check matrix and the degree distribution of the associated graph. Some common codes comprise, for example, regular LDPCs, irregular LDPCs, a Low Density Generator Matrix (LDGM) codes, Luby Transform (LT) codes, Raptor codes, etc.
Further, the dimensions of an LDPC parity check matrix may be pre-determined or may be changed on the fly as new output symbols are generated, for example in the case of LT codes and Raptor codes.
Two or more LDPC codes may also be cascaded for various reasons that include, but are not limited to, better decoding performance, lower complexity, ease of encoding, etc.
In all cases, the receiving end must know the particular parity check matrix of each constituent code for setting up the correct graph for message-passing decoding. The parity check matrix has thus to be signaled to the receiving end.
The LDPC codes are particularly efficient when they are adapted to encode large blocks of data. For example, the block length is typically a few thousands of data symbols. Accordingly, the number of elements in the parity check matrix is very large, typically a few millions. It is therefore of importance that the parity check matrix is signaled in an efficient manner to the receiving end.
The Asynchronous Layered Coding (ALC) Protocol Instantiation is a base protocol at the application layer that supports a massively scalable, reliable multicast transport of arbitrary binary objects. ALC is defined for example in the document RFC 3450: “Asynchronous Layered Coding (ALC) Protocol Instantiation”, December 2002, which is incorporated by reference herein. The File Delivery over Unidirectional Transport (FLUTE) protocol is a multicast transport protocol that builds on ALC. The FLUTE protocol ensures specifically for file deliveries that the receiving ends know what the transmitted objects actually represent. The FLUTE protocol provides a mechanism for signaling and mapping the properties of files to the concepts of ALC in a way that allows receivers to assign those parameters for received objects. FLUTE is defined for example in the document RFC 3926: “FLUTE—File Delivery over Unidirectional Transport”, October 2004, which is equally incorporated by reference herein.
Both ALC and FLUTE recommend the use of a FEC building block for providing a reliable transport of files over unreliable unidirectional point-to-multipoint links.
The overall ALC packet format is shown in FIG. 1.
An ALC packet comprises a User Datagram Protocol (UDP) header, an LCT packet header, an FEC Payload ID portion and an Encoding Symbols portion.
Encoding symbols are what the receiving end uses to reconstruct an object.
A default LCT packet header comprises as required sections an array of flags, an LCT header length field HDR_LEN, a Codepoint (CP) field and a Congestion Control Information (CCI). In addition, the LCT packet header may comprise optional sections, including for example Transport Object Identifier (TOI) fields. Moreover, header extensions can be used to extend the LCT header portion. The presence of header extensions can be inferred by prior fields in the LCT header, for example the LCT header length field HDR_LEN. One defined Protocol Instantiation specific extension is the FEC Object Transmission Information (FEC OTI) extension EXT_FTI. The LCT header format including the required fields, optional fields and header extensions is presented in FIG. 2. The LCT header is described in more detail in the document RFC 3451: “Layered Coding Transport (LCT) Building Block”, December 2002, which is incorporated by reference herein.
The CodePoint (CP) field of the LCT header can be used for signaling an FEC Encoding Identifier (ID). The FEC Encoding ID specifies an employed FEC scheme in a broader sense, for example ‘No-Code’, a Reed-Solomon code ‘RS’, an ‘LDGM’ code, a Raptor code, etc.
The FEC Payload ID of the ALC packet is used to identify an FEC Encoding Symbol with respect to the particular FEC scheme and the associated source-blocking algorithm. Obviously, the FEC Payload ID depends on the FEC Encoding ID. For example, in the case of a ‘No-Code’ FEC defined by the FEC Encoding ID, the FEC Payload ID comprises only a Source Block Number (SBN) and an Encoding Symbol ID (ESI). The SBN identifies from which source block of the object the encoding symbols in the payload are generated, while the ESI identifies which specific encoding symbols generated from the source block are carried in the packet payload.
Even for a given FEC Encoding ID, various implementations of the codec may be possible. For example, when RS codes are used, two known implementations are possible: a Vandermonde matrix based implementation and a Cauchy matrix based implementation. For this case, a FEC Instance ID is associated to the FEC Encoding ID, which signals a specific implementation type.
Apart from this information, a set of parameters specific to a particular FEC algorithm must be signaled to the receiving end, including the elements of the parity check matrix associated to an employed FEC code. A FEC building block of ALC has a provision to signal this information in the form of FEC Object Transmission Information (FEC OTI).
The above cited document RFC 3926 provides more specifically that the FEC OTI information is transmitted either in the separate header extension EXT_FTI or in an FDT Instance object.
An EXT_FTI field for FEC OTI may be included in all ALC packets of a delivery session or in a subset of these ALC packets. As indicated above, the field HDR_LEN, for example, may signal whether EXT_FTI for FEC OTI is included in a particular ALC packet. The format of the EXT_FTI is defined in the above cited document RFC 3926, according to which it comprises a general EXT_FTI format followed by a specific EXT_FTI format corresponding to the FEC Encoding ID. The EXT_FTI format for including the FEC OTI is presented in FIG. 3. The FEC OTI can be included in the indicated “FEC Encoding ID specific format” portion of a corresponding EXT_FTI. The FEC OTI can be included in the EXT_FTI of any ALC packet, if it is rather small.
If the FEC OTI is quite long, in contrast, it is preferably signaled as part of an FDT Instance.
In general, an FDT provides a means to describe various attributes associated with files that are to be delivered within a file delivery session. Within the file delivery session, the FDT is delivered as FDT Instances. An FDT Instance of FLUTE typically consists of general information about each of the files transmitted in the current session. This information is conveyed in the encoding symbols portion of the ALC packet using an extensible Markup Language (XML) schema. The FDT Instance describes at least the two attributes TOI and URI of each file. Additionally it may describe other attributes of each file, like Content-Encoding, Content-Type, and Transfer-Length, etc. In addition, each FDT Instance must have a header extension of the LCT header called EXT_FDT that contains an FDT Instance ID. The FDT Instance ID is used to uniquely identify an FDT Instance in-a session.
If the FEC OTI is included in the FDT, the FDT Instance may span over several ALC packets. The information in the FDT Instance packets is very critical for the recovery of the entire file. Therefore, they must be reliably communicated to all receiving ends. This can be achieved by carousel or by FEC, that is, by protecting the group of packets belonging to an FDT Instance by an FEC scheme. The parameters of the FEC scheme used to protect the FDT Instance packets can be signaled to the receiving ends.
For signaling the required parity check matrix in the FEC OTI with a small amount of data to a receiving end, it has been proposed for Raptor codes that only a 4-byte KEY is included in every ALC packet, in order to provide the receiving end with information on how to generate one column of the parity check matrix. The generation of the parity check matrix from a KEY is not straightforward, though. It involves the use of a random number generator and a series of XOR operations.
Further, it has been proposed to use a virtual machine that can run a bytecode for the generation of an LDPC parity check matrix at the receiving end. The bytecode consists of a set of instructions for the virtual machine. The bytecode size is a few hundred Bytes for simple regular LDGM codes. For irregular LDPC codes and Raptor codes, the bytecode may be much longer. The bytecode may be sent as a part of the FEC OTI. It is a disadvantage of this approach that the bytecode instructions for a virtual machine can be complex and may consume a significant amount of computational resources at the receiving end.
Both approaches thus have the drawback that the generation of the parity check matrix at the decoder could make the decoder more complex.